﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//思路
//建立一个p大小的窗口，在s上面滑动，不断判断是不是异位词
public class Solution438
{
    public IList<int> FindAnagrams2(string s, string p)
    {
        IList<int> res= new List<int>();
        int winSize=p.Length;
        //加速，有一个没有的话，不从下一个开始，直接跳两个
        for (int i = 0; i < s.Length-winSize+1; i++) {

            if (Check(s, p, i))
            {

                res.Add(i);
                Console.WriteLine("s[i]"+s[i]);
            }
        
        }

        return res;


    }
    //这个检查方式，会导致bab符合abc的要求---解决办法，visted数组
    //baa和aa，第一个a会把所有的a都访问,---解决办法，提前break
    //超时，---解决办法，提前break

    private bool Check(string s, string p, int start)
    {
        int winSize = p.Length;
        bool[] visted= new bool[winSize];//记录p里面的是否使用过
        //Console.WriteLine(start);


        //挨个测试窗口
        for (int i = start; i < start+winSize; i++) {

            //依次检查p里面有没有字母s[i] 
            bool have =false;
            for (int j= 0; j < winSize; j++)
            {

               
                if (!visted[j])
                {
                    if (s[i] == p[j])
                    {
                        have = true;
                        visted[j] = true;
                        break;

                    }
                }

            }

                //检查p里面有没有字母当前的s[i] ，第一个没有直接就退出函数了
                if (!have)
            {
                return false;
            }
        }

        return true;
    }

    //统计数量就可以了
    public IList<int> FindAnagrams(string s, string p)
    {
        IList<int> res = new List<int>();
        int lens=s.Length;
        int lenp=p.Length;
        int winSize = p.Length;

        if (lens < lenp)
        {
            return res;
        }
        //先计算p的数字数量
        int[] p_count=new int[26];
        int[] s_count=new int[26];
        for (int i = 0; i < lenp; i++)
        {
            p_count[p[i] - 'a'] ++ ;
            s_count[s[i] - 'a'] ++ ;
        }

        if (Enumerable.SequenceEqual(s_count, p_count))
        {
            res.Add(0);//判断这两个数组是否一样
        }

        
        
        for (int i = 0; i < s.Length - winSize ; i++)
        {

            s_count[s[i] - 'a']--;//从窗口出去的减去
            s_count[s[i+ winSize] - 'a']++;//进去窗口加入

            if (Enumerable.SequenceEqual(s_count, p_count))
            {
                res.Add(i+1);//判断这两个数组是否一样
            }

        }

        return res;


    }
}
class Program438
{

    static void Main438(string[] args)
    {
        Solution438 solution = new Solution438();
        //string s = "cbaebabacd", p = "abc";
        string s = "abab", p = "ab";
        IList<int> res= solution.FindAnagrams(s, p);
        for (int i = 0; i < res.Count; i++)
        {
            Console.WriteLine(res[i]);
        }
    }
}
